use std::collections::HashMap;
use std::env;
use std::fmt::Debug;
use std::fs::File;
use std::hash::Hash;
use std::io::{BufRead, BufReader, Write};
use std::path::Path;

#[derive(Debug)]
struct TrieNode<K, V>
where
    K: Eq + Hash + Debug,
    V: Debug,
{
    children: HashMap<K, TrieNode<K, V>>,
    value: Option<V>,
}

#[derive(Debug)]
pub struct TrieTree<K, V>(TrieNode<K, V>)
where
    K: Eq + Hash + Debug,
    V: Debug;
#[derive(Debug)]
struct TrieTreeScanIter<'a, K, V, T>
where
    K: Eq + Hash + Debug,
    V: Debug,
    T: AsRef<[K]> + Debug,
{
    origin: T,
    root: &'a TrieNode<K, V>,
    current_node: &'a TrieNode<K, V>,
    current_idx: usize,
    backoff_value: Option<&'a V>,
    backoff_index: usize,
}

#[derive(Debug, Eq, PartialEq)]
pub enum ScanResult<V> {
    // 在字典中找到一个匹配的值
    Found(V),
    // 在字典中找不到一个匹配的值，返回原文字符 index
    NotFound(usize),
}

impl<'a, K, V, T> Iterator for TrieTreeScanIter<'a, K, V, T>
where
    K: Eq + Hash + Debug,
    V: Debug,
    T: AsRef<[K]> + Debug,
{
    type Item = ScanResult<&'a V>;

    fn next(&mut self) -> Option<Self::Item> {
        let origin = self.origin.as_ref();
        while self.current_idx < origin.len() {
            match self.current_node.children.get(&origin[self.current_idx]) {
                Some(child) => {
                    if child.value.is_some() {
                        self.backoff_index = self.current_idx;
                        self.backoff_value = child.value.as_ref();
                    }
                    self.current_node = child;
                    self.current_idx += 1;
                }
                None => {
                    self.backoff_index += 1;
                    self.current_idx = self.backoff_index;
                    self.current_node = self.root;
                    return match self.backoff_value.take() {
                        Some(v) => Some(ScanResult::Found(v)),
                        None => Some(ScanResult::NotFound(self.current_idx - 1)),
                    };
                }
            }
        }
        let result = match self.backoff_value.take() {
            Some(v) => Some(ScanResult::Found(v)),
            None => {
                if self.backoff_index < origin.len() {
                    Some(ScanResult::NotFound(self.backoff_index))
                } else {
                    None
                }
            }
        };
        self.backoff_index += 1;
        self.current_idx = self.backoff_index;
        self.current_node = self.root;
        result
    }
}
impl<K, V> Default for TrieNode<K, V>
where
    K: Eq + Hash + Debug,
    V: Debug,
{
    fn default() -> Self {
        Self {
            children: HashMap::default(),
            value: None,
        }
    }
}

impl<K, V> TrieTree<K, V>
where
    K: Eq + Hash + Debug,
    V: Debug,
{
    pub fn new() -> TrieTree<K, V> {
        TrieTree(TrieNode::default())
    }

    pub fn iter_scan(
        &self,
        origin: impl AsRef<[K]> + Debug,
    ) -> impl Iterator<Item = ScanResult<&V>> {
        TrieTreeScanIter {
            origin,
            root: &self.0,
            current_node: &self.0,
            current_idx: 0,
            backoff_value: None,
            backoff_index: 0,
        }
    }

    pub fn insert(&mut self, key: impl Iterator<Item = K>, value: V) {
        let node = key.fold(&mut self.0, |parent, k| {
            parent.children.entry(k).or_insert_with(TrieNode::default)
        });
        node.value = Some(value);
    }
}

pub fn tree_generator(mod_name: &str, input_file_names: &[&str]) {
    let dst =
        Path::new(&env::var("OUT_DIR").expect("OUT_DIR not set")).join(format!("{mod_name}.rs"));
    let mut output = File::create(dst).expect("Failed to create file");
    output
        .write(
            r#"
const DATA: &[(&str, &str)] = &[
"#
            .as_ref(),
        )
        .expect("failed to write file");
    for &input in input_file_names {
        let file = File::open(input).expect("failed to open file");
        let mut lines = BufReader::new(file).lines();
        while let Some(Ok(line)) = lines.next() {
            if line.is_empty() || line.starts_with('#') {
                continue;
            }
            println!("{line}");
            let mut line = line.split(":").map(|s| s.trim());
            let c = line.next().expect("failed to get char");
            let value = line.next().expect("failed to get value");
            write!(output, r#"    ("{c}", "{value}"),"#).expect("failed to write file");
            output.write(b"\n").expect("failed to write file");
        }
    }

    output
        .write(
            r#"
];
"#
            .as_ref(),
        )
        .expect("failed to write file");

    output.write(r#"
pub static SIGLETON: once_cell::sync::Lazy<utils::trie_tree::TrieTree<char, &'static str>> = once_cell::sync::Lazy::new(||{
    let mut tree = utils::trie_tree::TrieTree::new();
    DATA.iter().for_each(|(key, value)| {
        tree.insert(key.chars(), *value);
    });
    tree
});
"#.as_ref()).expect("failed to write file");
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_trie_tree() {
        let mut trie_tree = TrieTree::new();
        trie_tree.insert("ho".chars(), 1);
        trie_tree.insert("wd".chars(), 2);
        trie_tree.insert("howd".chars(), 3);
        trie_tree.insert("howd".chars(), 4);
        trie_tree.insert("h".chars(), 5);
        trie_tree.insert("abcd".chars(), 4);

        struct TestCases {
            input: &'static str,
            expect: Vec<ScanResult<&'static i32>>,
        }
        let cases = vec![
            TestCases {
                input: "ho",
                expect: vec![ScanResult::Found(&1)],
            },
            TestCases {
                input: "wd",
                expect: vec![ScanResult::Found(&2)],
            },
            TestCases {
                input: "howd",
                expect: vec![ScanResult::Found(&4)],
            },
            TestCases {
                input: "hohowdwdhhhhohwdw123ho",
                expect: vec![
                    ScanResult::Found(&1),
                    ScanResult::Found(&4),
                    ScanResult::Found(&2),
                    ScanResult::Found(&5),
                    ScanResult::Found(&5),
                    ScanResult::Found(&5),
                    ScanResult::Found(&1),
                    ScanResult::Found(&5),
                    ScanResult::Found(&2),
                    ScanResult::NotFound(16),
                    ScanResult::NotFound(17),
                    ScanResult::NotFound(18),
                    ScanResult::NotFound(19),
                    ScanResult::Found(&1),
                ],
            },
            TestCases {
                input: "1ho1",
                expect: vec![
                    ScanResult::NotFound(0),
                    ScanResult::Found(&1),
                    ScanResult::NotFound(3),
                ],
            },
            TestCases {
                input: "1ho",
                expect: vec![ScanResult::NotFound(0), ScanResult::Found(&1)],
            },
            TestCases {
                input: "ho1",
                expect: vec![ScanResult::Found(&1), ScanResult::NotFound(2)],
            },
            TestCases {
                input: "how",
                expect: vec![ScanResult::Found(&1), ScanResult::NotFound(2)],
            },
            TestCases {
                input: "abc",
                expect: vec![
                    ScanResult::NotFound(0),
                    ScanResult::NotFound(1),
                    ScanResult::NotFound(2),
                ],
            },
        ];
        for case in cases {
            let output = trie_tree
                .iter_scan(case.input.chars().collect::<Vec<_>>())
                .collect::<Vec<_>>();
            assert_eq!(output, case.expect);
        }
    }
}
